A Turing degree d bounds a principle P of reverse mathematics if everycomputable instance of P has a d-computable solution. P admits a universalinstance if there exists a computable instance such that every solution boundsP. We prove that the stable version of the ascending descending sequenceprinciple (SADS) as well as the stable version of the thin set theorem forpairs (STS(2)) do not admit a bound of low_2 degree. Therefore no principlebetween Ramsey's theorem for pairs RT22 and SADS or STS(2) admit a universalinstance. We construct a low_2 degree bounding the Erd\H{o}s-Moser theorem(EM), thereby showing that previous argument does not hold for EM. Finally, weprove that the only Delta^0_2 degree bounding a stable version of the rainbowRamsey theorem for pairs (SRRT22) is 0'. Hence no principle between the stableRamsey theorem for pairs SRT22 and SRRT22 admit a universal instance. Inparticular the stable version of the Erd\H{o}s-Moser theorem does not admitone. It remains unknown whether EM admits a universal instance.
展开▼
机译:如果P的每个可计算实例都具有d可计算解,则图灵度d限制了逆数学原理P。如果存在一个可计算的实例,使得每个解决方案都约束P,则P接受一个通用实例。我们证明了升序序列原理的稳定版本(SADS)以及薄集定理对的稳定版本(STS(2))不接受low_2度的界。因此,对RT22和SADS或STS(2)的拉姆西定理之间的原理都没有一个通用的例子。我们构造了一个以Erd \ H {o} s-Moser定理(EM)为边界的low_2度,从而表明先前的论点不适用于EM。最后,我们证明了限制对的RainbowRamsey定理(SRRT22)的稳定版本的唯一Delta ^ 0_2度是0'。因此,对SRT22和SRRT22的stableRamsey定理之间的任何原理都不允许通用实例。尤其是Erd \ H {o} s-Moser定理的稳定版本不容许。 EM是否接受通用实例仍然未知。
展开▼